n=1000;
q=1000;
index=[2092768,5542900,2983327,7841145,4046240,9978998,3372448,246100,5818619,9244327,7642696,9899044,770164,4673883,9829920,7019836,6036764,4641968,8325235,5537870,8878054,9320160,3325088,829880,8090575,8226680,6162495,3908391,1337988,7858120,4181824,3320892,9707422,8810973,5724690,8598860,9134250,4965775,6616010,8441160,3962912,854962,3962288,4557599,7969000,5598200,1173544,3299092,1379800,1082092,9704013,6743965,7365394,7322298,310232,1489504,9258048,1545368,5886472,3702082,2900720,2285966,5502668,8266562,4217550,6338300,5069226,50082,1624464,5347556,3547340,6513876,7015915,1263264,1870609,4685249,7360960,844190,7133860,5174197,7033587,3957878,6004140,8866692,7435296,1790784,648140,5813272,3438520,9587613,8303257,8539140,2712050,7966610,7787829,2381700,5597738,458352,6168558,6051164,7478760,1182310,2977098,6565201,8738768,6199985,5718265,4787386,4933894,1460562,45440,9640437,1128007,1026588,3954920,4698368,294400,7414160,4869044,3669206,1207899,2160984,5254900,8234738,1298312,138612,7377205,4924920,6218289,9762943,4150228,1101456,3711825,2494811,9234462,1157920,8365945,8119584,6626096,5028480,4280780,7879040,8102660,11507,2096321,2323968,4129875,5087017,7917953,3215135,7123496,3627700,1202031,5142350,1431736,5306430,3091696,5105750,8974655,651850,4454974,6635296,9721504,97350,1011710,4946501,4101285,36475,3538502,2083634,6864896,7110871,3105176,1177646,795456,6645738,5886992,316653,579424,7717388,4422152,1367056,2946874,3259765,8037004,8804705,6964613,8435304,5187991,1854184,7692000,657524,9470080,9384952,8103808,9134190,1233845,1603862,544906,245598,5871648,7949101,4296750,323280,351731,5863424,3000588,5528522,6670056,7928344,9327920,4728676,379860,7447225,8335380,3657000,6742280,6973219,313818,7641750,445904,5141220,524668,1048324,5228288,5640904,4318785,8698935,1956950,1257072,9660333,9573298,3645190,220957,641128,3559504,8195120,3498265,4865240,3221960,414282,1492555,8719551,6800035,2147741,1368248,1901003,415292,6295736,160024,1188317,1543154,3942656,8594980,6724921,8641631,5597838,8751546,5609560,44308,5197638,6914944,7442290,3013206,4027216,4067659,9116213,2465168,6885317,3248516,9167560,8428898,529531,3715100,6253467,6630909,361736,4721206,1461700,1504500,2956446,8712708,2140536,6161881,7752080,3941784,4375340,9849720,2713709,7901419,3638264,9553568,1232396,9546260,2116257,8861532,9129840,9573870,3134651,4044220,2542192,1024720,255984,6110672,9076869,8678748,5140205,8833980,8640686,1598616,1701440,1514634,6141798,3974763,659278,2999810,3941602,1635168,4440960,5435281,6171956,3514021,7638860,7227110,2191145,2207804,4493718,5676926,3066942,6851452,7888386,3162800,5074288,5286915,3304876,6445200,4724880,1790,9604888,9189408,3649112,919294,4489121,9173412,7439248,4998384,1269142,7535290,7500740,1798156,5293872,3068080,2578671,3355756,4613310,3901940,130977,1325862,8897441,2641830,4072759,1679993,2883987,6807065,4939158,6746250,3039488,1587562,9184065,9893925,9964080,5874778,8384031,5932952,6346505,579835,3565984,4947000,2050856,7217200,401835,2502226,4683874,4948360,8588542,1978889,8543125,66215,9469102,8623382,6323705,6758548,5107648,2069824,708114,3265801,9120576,9716450,5814031,125104,694776,882740,5879307,1704833,9181540,4777054,8828663,3111000,60380,7874135,5107392,9086655,8005515,8402257,9088018,6604536,6787936,9730944,6083880,4048924,3253376,4514212,651316,6217208,429534,3585014,9174242,77324,8707430,6827018,3793552,8181562,9372865,3893744,8410796,6222456,7350468,3887978,710640,5484811,7249550,4786816,8658028,2566353,5490788,8084631,2445248,9612800,2893171,9543816,5318593,2042739,8578600,2211326,9482459,7773199,8514320,7926165,3221958,3235300,2430879,4934145,5370332,4634545,6196362,3943088,6686100,7900584,5478109,936714,5674375,2087640,1643552,5530758,3238354,6432284,3309818,2419284,3123816,6030235,9925852,2079168,3350272,1731750,3500800,9692626,4320308,4324600,3585368,1845701,6286978,1987469,6157080,1063876,1026270,33275,1850886,5711772,1858915,4977776,1576796,6369776,6036592,6390624,5115894,3157248,5206608,7956124,4806981,6845220,5079704,9210483,9008551,3667112,5956843,9189970,9154063,4282072,3609100,1022712,6058330,5205239,2162951,7091150,4689173,1230888,7010753,695834,3303605,6048010,335299,9505045,2742804,9458320,268090,4367392,3754214,6528458,6930360,2084920,9698206,4381125,3397926,6631720,437000,3451264,9411688,7654137,3414063,7267865,5225490,2480356,3669908,8107322,6452682,8322900,1501942,3071207,9686448,7908895,6373396,1257954,9622325,7113818,1055368,8609645,7962593,2154752,7739836,4878070,2641995,4004426,6302350,5173512,3918303,6694809,9910675,8635787,8958984,5746304,2487488,9626008,3333546,5481483,4879184,2787296,133728,7679336,3585430,7393256,9818312,4870142,4273672,4370394,319540,7017164,4439872,9890248,3848652,9848160,4824168,7054493,928800,421306,2854073,1219422,2459343,4399335,3389752,4600742,8037288,5441200,1663392,9728088,1104400,4892615,8013794,4342113,8023200,7596366,9794678,9151077,3958954,9869572,9703488,6884084,1067488,4809356,3525713,1363440,2113311,190877,1445474,4634978,3885932,265679,1510378,9638385,4238175,1616488,547075,8016952,7553424,3117048,1444275,2002122,2291538,2411054,7600321,905160,2052816,5874047,3768018,9401323,6930720,5380208,1437414,748645,3089347,1765625,1386227,5738385,221686,7472750,7291100,2242160,7491284,9717700,3840440,5913510,6600785,6039624,4785568,52172,8906490,2780668,4484022,2114630,4204035,735481,4531424,8829450,4289197,2989936,8289514,9265036,2858660,2684416,4135134,2270530,1134080,4518810,7820244,7457697,3998987,6997298,5877512,8363785,7209508,877355,7485860,3488395,8632075,5482878,7381690,7203770,1729228,8709648,1746262,3203173,6798336,3492504,8117448,2365605,3281978,9417205,9952196,2444030,2242836,8463680,8818620,9371193,6658024,7433788,3847475,6449687,5063384,5084844,339732,451790,1234310,917920,8365230,3018722,9350460,3474750,2158990,6391688,5877417,4350152,523302,941874,9871648,7282200,7842112,9569677,8704598,7212188,9778560,4797026,3310569,4189305,9136650,1069648,5485327,9518934,4400899,5857420,8245917,1226600,4892780,9737465,1120112,3688144,5251140,78208,8492823,5676116,2757952,3992420,315768,191546,6791424,7978396,4288435,9192437,8642742,4596075,5962874,1327040,6866080,5591260,9399698,3269400,8696240,7759025,2900971,1444813,4678800,694302,4905624,8838572,8114750,4503658,5830409,6774150,8960714,658596,7136000,9203260,2792444,7876440,8172354,2764844,5183782,6680878,9389811,183600,3609765,4927964,2274440,1177080,5248241,8259756,4302800,650252,8713140,8470249,3783269,6078032,9846354,7445346,1444114,7222880,8346730,7438294,1791476,6040040,2619784,9116152,8839302,1901998,4824053,9211460,6551806,7575249,4587840,2864840,7180169,6191840,7956717,6922380,3082772,8804495,6010825,6709040,5770516,2296120,6618140,6237990,7197952,3254885,6605724,371725,5103160,2191204,3190944,5699790,6414000,9870452,9582060,1421826,270438,8456918,9360960,7195328,8333580,365798,3438320,2423231,9865754,2495072,5149950,4302953,8069344,1300104,8034700,5492928,2489551,9592304,5549876,2380295,1807288,8880086,3114288,3544784,1110528,102648,7855100,2634424,9941276,5950269,5033268,3372540,7812327,7648417,4073408,9298880,3019621,3294250,1183424,4950775,285584,2167745,5251666,3769208,8537050,6231520,6898299,9918870,4807710,4042300,4652545,7656464,3305211,754193,232625,3740816,8041718,8291940,1454828,5837523,1936706,8390776,7357440,2456376,8300950,5713350,3372985,2613600,2080246,8803800,3461300,240285,1825227,5573736,860270,776372,7769570,3452674,7848981,1827103,7801860,6739488,8642390,3434375,7488796,4374388,4690552,4851912,8367805,3250101,7526827,5901660,7667170,561712,6834125,5506764,9028330,2560471,623665,586330,2631105,659159,9180564,6470144,6716468,850084,3018459,9981469,4747930,8722952,8107920,3448551,6039220,4247448,5147176,806927,8359980,4764553,4225274,3733824,828229,1981440,445160,7532480,1244166,6920425,4712998,7888750,8236345,6640724,7467075,505059,6619164,6954468,4035154,4956196,5745734,4736685];
reader_token=[1,2,4,6,2,8,3,4,5,4,4,1,3,1,1,7,8,6,9,2,8,1,9,8,8,7,9,2,3,6,7,6,6,2,7,8,3,6,7,8,3,9,4,2,8,1,8,6,9,8,2,2,4,4,1,5,7,3,3,2,4,9,9,3,9,6,7,8,6,9,9,3,2,9,7,9,6,7,3,7,3,7,9,2,8,7,3,1,8,3,1,5,1,4,2,1,2,7,2,7,8,3,1,4,1,5,6,4,9,7,5,8,1,2,1,1,3,2,7,9,6,1,2,6,5,6,4,5,2,5,9,9,5,3,2,8,9,9,8,1,8,7,4,1,4,2,9,5,5,9,8,3,8,3,9,6,7,5,8,4,6,6,3,5,1,9,1,2,2,1,1,5,5,9,8,1,4,5,9,2,5,7,3,9,6,2,1,2,7,4,2,4,9,1,2,8,8,4,9,1,8,5,8,1,8,9,8,3,4,6,6,3,3,2,6,1,6,8,4,6,4,9,8,1,1,6,3,4,9,3,7,6,1,7,6,9,5,3,5,1,6,7,7,2,2,7,7,4,6,7,9,5,5,1,5,5,3,1,9,3,7,2,5,1,4,8,4,1,4,8,2,8,5,9,2,1,1,6,4,4,2,1,8,3,8,5,1,2,9,7,1,2,3,3,1,7,2,9,3,7,3,1,3,6,6,1,7,8,2,4,9,6,9,6,5,5,1,9,8,3,1,8,3,2,4,8,6,1,8,1,9,4,5,4,5,6,4,7,9,4,4,4,7,5,2,4,2,8,6,9,8,3,4,5,7,1,9,6,7,2,1,3,3,8,8,5,8,6,4,3,9,6,6,6,1,9,5,3,9,7,8,6,4,4,3,4,5,2,9,5,9,8,4,3,4,6,5,8,8,2,7,8,3,6,4,7,6,5,9,9,9,9,2,1,2,3,5,1,2,1,8,5,7,1,4,1,1,4,6,6,8,2,7,5,6,4,6,5,3,9,7,4,8,2,9,8,7,1,2,8,7,2,4,3,3,8,2,7,8,8,6,3,2,9,1,7,7,1,5,1,6,8,9,3,1,9,2,7,9,6,5,9,3,2,8,4,3,1,4,6,8,6,5,1,9,8,3,4,6,6,7,8,2,2,6,1,4,2,9,9,8,3,2,3,4,7,1,1,9,7,8,5,2,6,4,2,2,1,9,4,4,3,6,5,8,4,4,4,8,5,3,7,5,6,8,4,2,5,8,5,6,9,9,5,1,5,9,9,2,7,1,2,3,2,5,9,2,7,4,3,3,8,9,7,4,1,7,9,6,1,8,4,8,8,4,7,7,1,4,4,1,6,2,3,9,5,4,3,6,6,9,7,3,8,8,8,7,5,5,8,9,2,8,5,2,6,4,8,9,2,1,3,8,6,1,5,5,4,6,4,9,4,1,3,8,6,5,3,4,2,5,5,6,6,9,1,4,2,3,6,2,8,8,2,7,6,9,4,3,3,7,7,1,5,8,4,7,7,6,7,9,4,8,5,3,9,4,4,6,9,3,3,6,7,1,7,8,6,7,8,8,5,2,5,8,3,1,7,6,4,5,8,5,2,6,4,6,2,6,4,6,8,6,1,9,1,3,8,1,4,3,2,4,1,2,9,6,4,7,9,3,4,8,6,9,6,1,8,5,3,7,8,8,5,1,1,7,5,9,6,8,2,3,7,8,6,1,9,7,2,3,9,7,7,7,5,6,4,9,6,9,7,1,3,7,8,8,8,7,2,2,4,1,9,4,5,9,3,7,3,5,4,6,4,3,5,5,9,1,5,2,8,3,7,4,9,7,4,6,8,2,2,2,4,6,6,3,4,1,6,4,2,7,3,1,7,9,6,2,8,6,5,6,3,7,1,9,1,6,4,2,4,9,5,9,3,8,5,4,8,8,1,9,2,9,8,3,1,5,3,8,6,1,4,9,4,8,7,5,5,4,3,1,6,5,3,7,4,7,6,8,6,2,2,1,8,5,4,4,3,3,6,5,5,3,9,4,4,4,7,9,6,9,3,9,5,4,5,1,5,9,1,3,4,2,3,7,4,3,8,8,4,4,6,7,4,4,3,8,4,1,1,7,4,4,1,2,3,9,5,9,3,2,1,5,5,8,1,4,1,5,5,7,6,6,5,5,2,4,1,5,2,8,7,8,5,2,9,3,6,3,3,9,1,8,9,1,3,5,9,6,6,6,5,1,4,2,5,5,2,8,6,7,5,9,8,3,4,8,4];
reader_bit=[1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1];